package com.jack.leetcode.eachProblem08;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class 重新安排行程 {

    public List<String> findItinerary(List<List<String>> tickets) {
        if (tickets == null || tickets.isEmpty()) {
            return null;
        }
        Map<String, List<String>> graph = new HashMap<>();
        List<String> result = new LinkedList<>();
        for (List<String> ticket : tickets) {
            List<String> nbr = graph.computeIfAbsent(ticket.get(0), k -> new LinkedList<>());
            nbr.add(ticket.get(1));
        }
        graph.values().forEach(x -> x.sort(String::compareTo));
        visit(graph, "LFK", result);
        return result;
    }

    private void visit(Map<String, List<String>> graph, String src, List<String> result) {
        List<String> nbr = graph.get(src);
        while (nbr != null && nbr.size() > 0) {
            String remove = nbr.remove(0);
            visit(graph, remove, result);
        }
        result.add(0, src);
    }
}

